package com.xjj.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class M0210CourseScheduleII {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<>();
        // 记录入度
        int[] inEdges = new int[numCourses];
        // 初始化出边表
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        // 0 依赖于 1 那么 1->0
        for (int[] arr : prerequisites) {
            edges.get(arr[1]).add(arr[0]);
            inEdges[arr[0]]++;
        }
        // 入度为0的进队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inEdges[i] == 0) {
                queue.offer(i);
            }
        }
        int[] resultArr = new int[numCourses];
        int index = 0;
        while (!queue.isEmpty()) {
            // 入度为0(没前置的课)
            int course = queue.poll();
            resultArr[index++] = course;
            // 对应入边的点的入边可减1
            for (int c : edges.get(course)) {
                inEdges[c]--;
                if (inEdges[c] == 0) {
                    queue.offer(c);
                }
            }
        }
        boolean result = true;
        for (int count : inEdges) {
            if (count != 0) {
                result = false;
            }
        }
        return result ? resultArr : new int[0];
    }
}
